#include <bits/stdc++.h>
using namespace std;

/*
2901. 最长相邻不相等子序列 II
已解答
中等
相关标签
相关企业
提示
给定一个字符串数组 words ，和一个数组 groups ，两个数组长度都是 n 。

两个长度相等字符串的 汉明距离 定义为对应位置字符 不同 的数目。

你需要从下标 [0, 1, ..., n - 1] 中选出一个 最长子序列 ，将这个子序列记作长度为 k 的 [i0, i1, ..., ik - 1] ，它需要满足以下条件：

相邻 下标对应的 groups 值 不同。即，对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij] != groups[ij + 1] 。
对于所有 0 < j + 1 < k 的下标 j ，都满足 words[ij] 和 words[ij + 1] 的长度 相等 ，且两个字符串之间的 汉明距离 为 1 。
请你返回一个字符串数组，它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。

子序列 指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。

注意：words 中的字符串长度可能 不相等 。

 

示例 1：

输入：words = ["bab","dab","cab"], groups = [1,2,2]
输出：["bab","cab"]
解释：一个可行的子序列是 [0,2] 。
- groups[0] != groups[2]
- words[0].length == words[2].length 且它们之间的汉明距离为 1 。
所以一个可行的答案是 [words[0],words[2]] = ["bab","cab"] 。
另一个可行的子序列是 [0,1] 。
- groups[0] != groups[1]
- words[0].length = words[1].length 且它们之间的汉明距离为 1 。
所以另一个可行的答案是 [words[0],words[1]] = ["bab","dab"] 。
符合题意的最长子序列的长度为 2 。
示例 2：

输入：words = ["a","b","c","d"], groups = [1,2,3,4]
输出：["a","b","c","d"]
解释：我们选择子序列 [0,1,2,3] 。
它同时满足两个条件。
所以答案为 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"] 。
它是所有下标子序列里最长且满足所有条件的。
所以它是唯一的答案。
 

提示：

1 <= n == words.length == groups.length <= 1000
1 <= words[i].length <= 10
1 <= groups[i] <= n
words 中的字符串 互不相同 。
words[i] 只包含小写英文字母。
*/

class Solution {
public:
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int n = words.size();
        // 以 i 结尾的最长子序列长度
        vector<int> dp(n, 1);
        vector<int> next(n, -1);// 记录路径
        int max_len = 1; 
        int start_index = 0;

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (groups[i] != groups[j] && checkHamming(words[i], words[j])) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        next[i] = j;
                    }
                }
            }
            if (dp[i] > max_len) {
                max_len = dp[i];
                start_index = i;
            }
        }

        vector<string> ans;
        int cur = start_index;
        while (cur != -1) {
            ans.push_back(words[cur]);
            cur = next[cur];
        }
        return ans;
    }

    bool checkHamming(const string& a, const string& b) {
         if (a.length() != b.length()) return false;
        int diff = 0;
        for (int i = 0; i < a.length(); ++i) {
            if (a[i] != b[i]) {
                diff++;
                if (diff > 1) return false;
            }
        }
        return diff == 1;
    }
};


// 法二
class Solution {
public:
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        int n = words.size();
        // f_map: 哈希值 -> (max_f, j, max_f2, j2)
        // 其中 max_f/j 是当前最大长度和对应索引，max_f2/j2 是次大长度和对应索引
        unordered_map<long long, tuple<int, int, int, int>> f_map;
        vector<int> from(n, -1);  // 记录每个位置的前驱节点
        int global_max_f = 0, max_i = 0;  // 全局最大长度和起始索引

        // 从后向前遍历，便于构建前驱关系
        for (int i = n - 1; i >= 0; i--) {
            const string& w = words[i];
            int g = groups[i];

            // 计算字符串的哈希值（简单移位哈希）
            long long hash = 0;
            for (char ch : w) {
                hash = (hash << 5) | (ch & 31);  // 每个字符占5位
            }

            int f = 0;  // 当前以i结尾的最长子序列长度
            // 检查所有可能的变异字符串（每个位置字符被"涂黑"）
            for (int k = 0; k < w.size(); k++) {
                // 构造变异哈希：将第k位字符设为全1（31）
                long long h = hash | (31LL << (k * 5));
                
                // 从哈希表中获取该变异字符串的最大和次大记录
                auto& [max_f, j, max_f2, j2] = f_map[h];
                
                // 检查是否可以转移状态
                if (g != groups[j]) {  // 最大值的group不同
                    if (max_f > f) {
                        f = max_f;
                        from[i] = j;
                    }
                } else {  // 只能从次大值转移
                    if (max_f2 > f) {
                        f = max_f2;
                        from[i] = j2;
                    }
                }
            }

            f++;  // 包含当前字符串
            // 更新全局最大值
            if (f > global_max_f) {
                global_max_f = f;
                max_i = i;
            }

            // 更新所有变异字符串的哈希表记录
            for (int k = 0; k < w.size(); k++) {
                long long h = hash | (31LL << (k * 5));
                auto& [max_f, j, max_f2, j2] = f_map[h];
                
                // 更新最大值和次大值，确保它们的group不同
                if (f > max_f) {
                    if (g != groups[j]) {  // 当前group与最大值不同
                        max_f2 = max_f;
                        j2 = j;
                    }
                    max_f = f;
                    j = i;
                } else if (f > max_f2 && g != groups[j]) {  // 只能更新次大值
                    max_f2 = f;
                    j2 = i;
                }
            }
        }

        // 构建结果序列
        vector<string> ans(global_max_f);
        int i = max_i;
        for (int k = 0; k < global_max_f; k++) {
            ans[k] = words[i];
            i = from[i];
        }
        return ans;
    }
};